#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>

#define MEM_SIZE 8096
#define MIN_BLOCK_SIZE sizeof(Block)

typedef struct Block {
    size_t size;
    bool free;
    struct Block* next;
} Block;

static char mem[MEM_SIZE];
static Block* freeList = NULL;

void initMemory();
void* umalloc(size_t size);
void ufree(void* ptr);
void umerge();

void initMemory() {
    freeList = (Block*)mem;
    freeList->size = MEM_SIZE - sizeof(Block);
    freeList->free = true;
    freeList->next = NULL;
}

void* umalloc(size_t size) {
    if (size == 0 || size > MEM_SIZE - sizeof(Block))
        return NULL;

    Block* currentBlock = freeList;
    while (currentBlock != NULL) {
        if (currentBlock->free && currentBlock->size >= size) {
            if (currentBlock->size > size + MIN_BLOCK_SIZE) {
                Block* newBlock = (Block*)((char*)currentBlock + sizeof(Block) + size);
                newBlock->size = currentBlock->size - sizeof(Block) - size;
                newBlock->free = true;
                newBlock->next = currentBlock->next;

                currentBlock->size = size;
                currentBlock->next = newBlock;
            }
            currentBlock->free = false;
            return (char*)currentBlock + sizeof(Block);
        }
        currentBlock = currentBlock->next;
    }
    return NULL; 
}

void ufree(void* ptr) {
    if (ptr == NULL)
        return;

    Block* block = (Block*)((char*)ptr - sizeof(Block));
    block->free = true;
}

void umerge() {
    Block* currentBlock = freeList;
    while (currentBlock != NULL && currentBlock->next != NULL) {
        if (currentBlock->free && currentBlock->next->free) {
            currentBlock->size += currentBlock->next->size + sizeof(Block);
            currentBlock->next = currentBlock->next->next;
        } else {
            currentBlock = currentBlock->next;
        }
    }
}

int main() {
    initMemory();

    // 测试代码
    void* ptr1 = umalloc(1000);
    void* ptr2 = umalloc(500);
    ufree(ptr1);
    umerge();
    void* ptr3 = umalloc(800);

    // 打印内存区块的情况
    Block* currentBlock = freeList;
    while (currentBlock != NULL) {
        printf("Block: %p, Size: %zu, Free: %s\n", 
               currentBlock, 
               currentBlock->size,
               currentBlock->free ? "true" : "false");
        currentBlock = currentBlock->next;
    }

    return 0;
}

